package com.roy.galaxy.algorithm;

/**
 * @author gang.wang1903@xiaobao100.cn
 * @Date: 2019-10-23 09:22
 * 返回最长的回文子字符串
 */
public class 最长回文字符串 {


    /**
     * 方法一：暴力时间解决,时间复杂度最高o(n^3),空间复杂度o(1)
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {

        String maxSubString = "";
        int len = s.length();
        if(len == 1){
            return s;
        }
        for(int i = 0 ; i < len ; i++){

            for(int j = i+1 ; j < len +1 ; j++){

                String subString = s.substring(i,j);
                if(subString.length() == 1 && subString.length() > maxSubString.length()){
                    maxSubString = subString;
                    continue;
                }
                if(isHuiWen(subString)){
                    if(subString.length() > maxSubString.length()){
                        maxSubString = subString;
                    }
                }
            }
        }

        return maxSubString;
    }


    public static boolean isHuiWen(String text) {
         int length = text.length();
         for (int i = 0; i < length / 2; i++) {
                 if (text.toCharArray()[i] != text.toCharArray()[length - i - 1]) {
                         return false;
                     }
             }
         return true;
     }

    public static void main(String[] args) {
        String text = "gphyvqruxjmwhonjjrgumxjhfyupajxbjgthzdvrdqmdouuukeaxhjumkmmhdglqrrohydrmbvtuwstgkobyzjjtdtjroqpyusfsbjlusekghtfbdctvgmqzeybnwzlhdnhwzptgkzmujfldoiejmvxnorvbiubfflygrkedyirienybosqzrkbpcfidvkkafftgzwrcitqizelhfsruwmtrgaocjcyxdkovtdennrkmxwpdsxpxuarhgusizmwakrmhdwcgvfljhzcskclgrvvbrkesojyhofwqiwhiupujmkcvlywjtmbncurxxmpdskupyvvweuhbsnanzfioirecfxvmgcpwrpmbhmkdtckhvbxnsbcifhqwjjczfokovpqyjmbywtpaqcfjowxnmtirdsfeujyogbzjnjcmqyzciwjqxxgrxblvqbutqittroqadqlsdzihngpfpjovbkpeveidjpfjktavvwurqrgqdomiibfgqxwybcyovysydxyyymmiuwovnevzsjisdwgkcbsookbarezbhnwyqthcvzyodbcwjptvigcphawzxouixhbpezzirbhvomqhxkfdbokblqmrhhioyqubpyqhjrnwhjxsrodtblqxkhezubprqftrqcyrzwywqrgockioqdmzuqjkpmsyohtlcnesbgzqhkalwixfcgyeqdzhnnlzawrdgskurcxfbekbspupbduxqxjeczpmdvssikbivjhinaopbabrmvscthvoqqbkgekcgyrelxkwoawpbrcbszelnxlyikbulgmlwyffurimlfxurjsbzgddxbgqpcdsuutfiivjbyqzhprdqhahpgenjkbiukurvdwapuewrbehczrtswubthodv";
       System.out.print( new 最长回文字符串().longestPalindrome(text));
    }

}
